
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1682. -- [Usaco2005 Mar]Out of Hay -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1682: [Usaco2005 Mar]Out of Hay</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>155&nbsp;&nbsp;<span class=green>Solved: </span>108<br>[<a href='submitpage.php?id=1682'>Submit</a>][<a href='problemstatus.php?id=1682'>Status</a>][<a href='bbs.php?id=1682'>Discuss</a>]</center><h2>Description</h2><div class=content>The cows have run out of hay, a horrible event that must be remedied
immediately. Bessie intends to visit the other farms to survey their
hay situation. There are N (2 <= N <= 2,000) farms (numbered 1..N);
Bessie starts at Farm 1.  She'll traverse some or all of the M (1
<= M <= 10,000) two-way roads whose length does not exceed 1,000,000,000
that connect the farms. Some farms may be multiply connected with
different length roads. All farms are connected one way or another
to Farm 1.

Bessie is trying to decide how large a waterskin she will need.  She knows
that she needs one ounce of water for each unit of length of a road. Since
she can get more water at each farm, she's only concerned about the length
of the longest road. Of course, she plans her route between farms such that
she minimizes the amount of water she must carry.

Help Bessie know the largest amount of water she will ever have to
carry: what is the length of longest road she'll have to travel
between any two farms, presuming she chooses routes that minimize
that number? This means, of course, that she might backtrack over
a road in order to minimize the length of the longest road she'll have
to traverse.


给出一个图,求最小生成树,要求最长边最短.
</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers, N and M.

* Lines 2..1+M: Line i+1 contains three space-separated integers, A_i,
        B_i, and L_i, describing a road from A_i to B_i of length L_i.

</div><h2>Output</h2><div class=content>* Line 1: A single integer that is the length of the longest road
        required to be traversed.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 3<br />
1 2 23<br />
2 3 1000<br />
1 3 43<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>43<br />
<br />
OUTPUT DETAILS:<br />
<br />
In order to reach farm 2, Bessie travels along a road of length 23.<br />
To reach farm 3, Bessie travels along a road of length 43.  With<br />
capacity 43, she can travel along these roads provided that she<br />
refills her tank to maximum capacity before she starts down a road.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1682'>Submit</a>][<a href='problemstatus.php?id=1682'>Status</a>][<a href='bbs.php?id=1682'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
